COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00024 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}
\baselineskip 14pt
\rm
\line{\sevenrm a62 tex[154,phy] \today\hfill}

\parskip 5pt
\line{\bf Fixed Point Theory\hfil}

\medskip
In what follows, there is some fixed domain {\bf U}. All roman capitals
designate members of ${\cal P}({\bf U})$, i.e., subsets of~$U$. Early letters
are fixed sets; late letters $X$, $Y$, $Z$, etc., are variables. Functions
$f$, $g$, $h$, and~$k$ are functions on ${\cal P}({\bf U})$; $f$~and $g$
are assumed monotone: $X\subseteq Y$ implies $f(X)\subseteq f(Y)$.
Script capitals, like ${\cal C}$ and ${\cal E}$, are subsets of
${\cal P}({\bf U})$, i.e., classes of subsets of~{\bf U}.

We use $h({\cal C})$ as a shorthand for the class $\{\,h(X)\mid X\in{\cal C}\,\}$;
$\bigcap {\cal C}$ for $\bigcap↓{X\in{\cal C}}X$, $\bigcup{\cal C}$ for 
$\bigcup↓{X\in{\cal C}}X$.

Most proofs are valid if ${\cal P}({\bf U})$ is replaced by an arbitrary
complete lattice, with $\bigcap$ and $\bigcup$ as GLB and LUB.

\proclaim Lemma. $f(\bigcap{\cal A})\subseteq \bigcup f({\cal A})$.

\noindent {\bf Proof.} 
$f(\bigcap{\cal A})\cap\bigcap f({\cal A})=f(\bigcap{\cal A})\cap 
\bigcap↓{X\in{\cal A}}
f(X)=\bigcap↓{X\in{\cal A}}\bigl(f(\bigcap {\cal A})\cap f(X)\bigr)
=\bigcap↓{X\in{\cal A}}f(\bigcap {\cal A})=\bigcap f({\cal A})$.
\quad\blackslug

Dually, $f(\bigcup {\cal A})\supseteq \bigcup f({\cal A})$.

Define ${\cal C}={\cal C}↓f$, the class of {\sl contractors\/} of~$f$,
as $\{\,X\mid f(X)\subseteq X\,\}$. 
Define $L=L↓f=\bigcap{\cal C}$. Then
$f(L)=f(\bigcap{\cal C})\subseteq\bigcap f({\cal C})=\bigcap↓{X\in{\cal C}}
f(X)\subseteq \bigcap↓{X\in{\cal C}}X=L$; 
$f(L)\subseteq L$, $f\bigl(f(L)\bigr)\subseteq f(L)$,
$f(L)\in{\cal C}$, $L=\bigcap{\cal C}\subseteq f(L)$, $L=f(L)$.
If $X\in{\cal C}$, $L=\bigcap {\cal C}\subseteq X$; $L$~is the unique
{\sl least contractor\/} (LC) of~$f$.

Define $Q=Q↓f$, the class of {\sl fixed points\/} of~$f$ as
$\{\,X\mid f(X)=X\,\}$; $Q\subseteq {\cal C}$; $L\in Q$, so $L$ is also
the unique {\sl least fixed point\/} (LFP) of~$f$. This has shown a variant
of the Tarski-Knaster fixed point theorem:

\proclaim Theorem. The intersection of the contractors of a monotone
function is, uniquely, the least contractor and least fixed point
(LFPC, LFP, LC) of the function.

\smallskip
{\rmn

\disleft 38pt::{\bf Drill.}
Could ${\cal C}$ be empty?

}

\smallskip
{\rmn

\disleft 38pt::{\bf Drill.}
Define ${\cal E}={\cal E}↓f=\{\,X\mid X\subseteq f(X)\,\}$ as the class
of {\sl expanders\/} of~$f$.
By a dual proof, exhibit a greatest expander and fixed point of a monotone
function.

}

\smallskip
If $\overline{Y}↓i=\langle Y↓{i1},Y↓{i2},\ldots,Y↓{in}\rangle$ are
$n$tuples of sets, define $\overline{Y}↓i\subseteq \overline{Y}↓j$ iff
for all~$k$, $Y↓{ik}\subseteq Y↓{jk}$. Define
$$\bigcap↓iY↓i=\left\langle\bigcap↓iY↓{i1},\bigcap↓iY↓{i2},\ldots,\bigcap↓i 
Y↓{in}\right\rangle\,.$$
If $\overline{f}=\langle f↓1,f↓2,\ldots,f↓n\rangle$, define
$$\overline{f}(\overline{Y})=\langle f↓1(\overline{Y}),f↓2(\overline{Y}),
\ldots,f↓n(\overline{Y})\rangle\,;$$
{}$\overline{F}$~is monotone iff all its components are.

For each fixed~$Y$, the inclusion $f(X,Y)\subseteq X$ has a LFPC
$\hat{f}(Y)=\bigcap\{\,X\mid f(X,Y)\subseteq X\,\}$; 
$f\bigl(\hat{f}(Y),Y\bigr)=\hat{f}(Y)$. If $Y↓1\subseteq Y↓2$, 
$f(X,Y↓2)\subseteq X$ implies $f(X,Y)\subseteq X$, so
${\cal C}(Y↓2)\subseteq {\cal C}(Y↓1)$, $\bigcap{\cal C}(Y↓1)\subseteq \bigcap
{\cal C}(Y↓2)$, $\hat{f}(Y↓1)\subseteq \hat{f}(Y↓2)$, and $\hat{f}$ is
monotone.

Take the two simultaneous inclusions
$$\left.\eqalign{%
f(X,Y)&\subseteq X\cr
g(Y,X)&\subseteq Y\,.\cr}\qquad\right\}\eqno(\ast)$$
We know that for all $X$ and $Y$
$$\eqalign{f\bigl(\hat{f}(Y),Y\bigr)&=\hat{f}(Y)\cr
g\bigl(\hat{g}(X),X\bigr)&=\hat{g}(X)\,.\cr}$$
Let $Z=A$ be the LFPC of $\hat{f}\bigl(\hat{g}(Z)\bigr)\subseteq Z$, so
$\hat{f}\bigl(\hat{g}(A)\bigr)=A$. Let $B=\hat{g}(A)$; then
$A=\hat{f}(B)$, and $\langle X,Y\rangle =\langle A,B\rangle$ satisfies
$(\ast)$ with equality. If $\langle X,Y\rangle=\langle C,D\rangle$
satisfies~$(\ast)$,
$$\eqalign{&f(C,D)\subseteq C;\quad \hat{f}(D)\subseteq C\cr
&g(D,C)\subseteq D;\quad \hat{g}(C)\subseteq D\cr
&\hat{f}\bigl(\hat{g}(C\bigr)\subseteq\hat{f}(D)\subseteq C;
\quad A\subseteq C\cr
&B=\hat{g}(A)\subseteq \hat{g}(C)\subseteq D\cr}$$
so $\langle A,B\rangle$ is the unique LFPC of $(\ast)$. Letting
$\overline{Y}$, $\overline{B}$, and $\overline{D}$ be $n$tuples, and
$g$ an $n$tuple of functions, we find (by induction) a LFPC for $n+1$
simultaneous inclusions, so the theorem generalizes to any number of
inclusions or equations.

Taking $\overline{Y}$, $\overline{B}$, $\overline{D}$ above as $n$tuples
of sets, we have the induction step of a proof that $n$ simultaneous
inclusions,
$$\overline{f}(\overline{X})\subseteq X\,,$$
have a unique LFPC. The reader may want first to read the above proof
with $\overline{Y}$, $\overline{B}$, and $\overline{D}$ as sets, proving
the result for $n=2$. Trusting readers may want to assume that $n=3$ and
$n=4$ are not very different.

When we need a value of $X$ that satisfies both inclusions
$$\left.\eqalign{%
A&\subseteq X\cr
f(X)&\subseteq X   \cr}\qquad\right\}\eqno(\ast\ast)$$
we can rewrite the condition as
$$A\cup f(X)\subseteq X\,,$$
which is monotone, so for each $A$ there is a least solution
$f↑{\ast}(A)=\bigcap\{\,X\mid f(X)\subseteq X\wedge A\subseteq X\,\}$;
$f↑{\ast}(A)=A\cup f\bigl(f↑{\ast}(A)\bigr)$.

\smallskip
{\rmn

\disleft 38pt::{\bf Drill.}
Show $f↑{\ast}$ is monotone.

}

\smallskip
{\rmn

\disleft 38pt::{\bf Exercise.}
Show $\bigcup↓{i≥0}f↑{(i)}(A)\subseteq f↑{\ast}(A)$, and that the
inclusion may be strict.

}

\vfill\eject

%\smallskip
The simultaneous relations
$$\left.\eqalign{%
f(X)&\subseteq X\cr
g(Y,X)&\subseteq Y   \cr}\qquad\right\}\eqno(\ast\ast\ast)$$
may be satisfied by $X=A=L↓f$, $Y=B=\hat{g}(A)$; $A=f(A)$, $B=g(B,A)$.
If $X=C$, $Y=D$ satisfies $(\ast\ast\ast)$,
$$\eqalign{&f(C)\subseteq C,\quad A\subset C\cr
&g(D,A)\subseteq g(D,C)\subseteq D,\quad B=\hat{g}(A)\subseteq D\,,\cr}$$
so $\langle A,B\rangle$ is a LFPC of $(\ast\ast\ast)$,
and $A$ may be found from the first relation of $(\ast)$
when $Y$ does not appear in it.

\smallskip
{\rmn

\disleft 38pt::{\bf Exercise.}
Generalize to more than two inclusions.

}

\smallskip
All the above results about fixed points and contractors may be dualized,
interchanging $\cap$ with~$\cup$, $\subseteq$ with $\supseteq$, least
contractors with greatest expanders, etc.

If $\{f↓i\}$ is a set of monotone functions on languages, a set of languages
may be specified by the simultaneous inclusions
$$L↓i\supseteq f↓i(L↓1,L↓2,\ldots,L↓n)\,.$$
While this system may not have a unique solution, it always has a unique
least solution, which satisfies the inclusions with equality. The inclusions
therefore may be written as equations.

If the functions $f↓i$ are constructed from the variables $L↓1,L↓2,\ldots,L↓n$
and finite languages combined by union and concatenation, the languages
defined are called XXXXX languages (also {\sl context free\/} and Type~2).
Allowing iteration in~$f↓i$ does not define any more languages, because
an equation like
$$X\supseteq Y↑{\ast}$$
can be replaced by
$$X\supseteq \Lambda\cup XY\,.$$
The least solution of a system satisfies the first of these equations with
equality, so it satisfies the second. Conversely, for any value of~$Y$,
the least solution~$X$ of the second equation is $X=Y↑{\ast}$.

\smallskip
{\rmn

\disleft 38pt::({\bf Exercise($\ast$).}
Prove this rigorously.)

}

\smallskip
{\rmn

\disleft 38pt::({\bf Drill.}
Suppose $\Lambda\in Y$, $Y↑{\ast}≠\Sigma↑{\ast}$. Show there
are at least two solutions of $X=\Lambda\cup XY$.)

}

\smallskip
\noindent
{\bf Example.}
$P\supseteq \Lambda\cup\{a\}P\{b\}$ has least solution $P=\{\,a↑ib↑i\mid i≥0\,\}$.

\smallskip
\noindent
{\bf Example.}
$$\eqalign{E&\supseteq T\cup E\;\hbox{\bf +}\;T\cr
T&\supseteq F\cup T \hbox{\bf $\times$}F\cr
F&\supseteq {\bf x}\cup {\bf y}\cup {\bf z}\cup \hbox{\bf (}E\hbox{\bf )}\cr}$$
where {\bf x} stands for the singleton language $\{x\}$, etc.
These inclusions require that the variables $x$, $y$, and $z$ belong to~$F$,
and so to~$T$ and~$E$. Then $x\times y$ belongs to~$T$, and so to~$E$;
$x\times y\times z$ belongs to~$T$; $x\times y+x\times y+z$ belongs to~$E$;
and $x\times y+x\times y\times z+y$ belongs to~$E$. This system has many
solutions, but only the least solution holds with equality. It could be
written
$$\eqalign{E&=T[\hbox{\bf +}T]↑{\ast}\cr
T&=F[\hbox{\bf $\times$} F]↑{\ast}\cr
F&={\bf x}\cup {\bf y}\cup {\bf z}\cup \hbox{\bf (}E\hbox{\bf )}\cr}$$
with the same least solution. 

\bigskip\bigskip

\line{\bf $\ast$ Recursive Definition Without Continuity.\hfil}

\smallskip
Let {\bf U} be an arbitrary domain, {\bf F} the class of partial functions
on~{\bf U}. We view a partial function as a set of ordered pairs, i.e.,
as a subset of ${\bf U}\times {\bf U}$. Let $t$ be a monotone mapping 
on~{\bf F}. We can not apply the Tarski-Knaster theorem directly, because
{\bf F} is not a power set; it is not closed under union. (Lattice
theorists: it is not a lattice, it does not have LUBs.) But we can extend
$t$ to a mapping~$\tau$ on ${\cal P}({\bf U}\times{\bf U})$.
Let ${\cal S}={\cal S}↓r=\{\,f\in F\mid f\subseteq r\,\}$,
$\tau(r)=\bigcup t({\cal S})$; 
$\langle x,y\rangle\in\tau(r)$ iff $\langle x,y\rangle\in t(f)$
for some $f\in S↓r$.
If $r\in{\bf F}$, $\tau(r)=t(r)$, so $\tau$ extends~$t$; $\tau$~is clearly
monotone. Let ${\cal C}=\{\,r\mid\tau(r)\subseteq r\,\}$;
$\rho =\bigcap{\cal C}$ is the unique LFP of~$\tau$. Next we show
$\rho\in{\bf F}$.

Let $\phi$ be the ``well-defined part'' of~$\rho$. That is, $\phi$~consists
of those pairs $\langle x,y\rangle$ for which $|x\rho|=1$. Any partial
function $f\subseteq \rho$ can  be extended to $f\cup\phi$, which is 
a partial function and a subset of~$\rho$.

If $\langle x,y↓1\rangle\in\rho=\tau(\rho)$, there is some $f\in{\bf F}$
for which $f\subseteq\rho$, $\langle x,y↓1\rangle\in t(f)=\tau(f)$.
Then $f\cup\phi\in{\bf F}$, $\langle x,y↓1\rangle\in\tau(f\cup\phi)=
t(f\cup\phi)$. If $\langle x,y↓2\rangle\in\tau(\phi)$, then also
$\langle x,y↓2\rangle\in t(f\cup\phi)$; since
$t(f\cup\phi)\in{\bf F}$, $y↓1=y↓2$; $\tau(\phi)$ contains only pairs
$\langle x,y\rangle$ for which $|x\rho|=1$. Then $\tau(\phi)\subseteq
\tau(\rho)=\rho$, $\tau(\phi)=t(\phi)\subseteq\phi$, $\phi$~is  
a contractor of~$\tau$, $\rho={\rm LC}↓{\tau}\subseteq \phi$, 
$\rho=\phi\in{\bf F}$.

\proclaim Theorem. If $t$ is a monotone mapping on {\bf F}, there is a unique
least solution $\rho\in{\bf F}$ of $t(\rho)\subseteq\rho$, which is also
the unique least solution of $t(\rho)=\rho$.

If {\bf U} is finite, the inclusion $f(X)\subseteq X$ can be solved for
its LC in finitely many steps. Let $X↓0=\emptyset$,
$X↓{i+1}=f(X↓i)$. By induction, $X↓i\subseteq X↓{i+1}$. The cardinalities
$|X↓i|$ can not always increase, because $|X↓i|≤|{\bf U}|$.
If $L$ is the LFPC, $X↓0=\emptyset\subseteq L$, and $X↓i\subseteq L$
implies $X↓{i+1}=f(X↓i)\subseteq f(L)=L$, so each $X↓i\subseteq L$.
When $|X↓i|=|X↓{i+1}|$, $X↓i=X↓{i+1}$ is a FP of the inclusion, and
must be the LFPC.

If {\bf U} is infinite, there is an analogous process that may find a LFP
of $f(X)\supseteq X$. Let $X↓0=\emptyset$, $X↓{i+1}=f(X↓i)$ as before; each
$X↓i\subseteq L↓f$. If all the $X↓i$ are different, define $X↓∞=\bigcup X↓i$;
$X↓∞\subseteq L↓f$. Then define $X↓{∞+i+1}=f(X↓{∞+i})$ to get another
sequence of sets $X↓{∞+i}$ included in~$L↓f$. If they are all different,
let $X↓{2∞}=\bigcup X↓{∞+i}$. Similarly one gets $X↓{j∞+i}$ for all~$i$
and $j≥0$. If they are all different, let $X↓{∞↑2}=\bigcup X↓{j∞}$.
The ``sequence'' goes on to $X↓{k∞↑2+j∞+i}$, to $X↓{∞↑3}=\bigcup X↓{k∞2}$,
and so on through all the polynomials in~$∞$.

\smallskip
{\rmn

\disleft 38pt::{\bf Drill.}
Why is $X↓∞\subseteq X↓{∞+1}$?

\disleft 38pt::({\bf Answer.} For each $i$, $X↓{∞+1}=f(X↓∞)\supseteq f(X↓i)
\supseteq X↓{i+1}$, $X↓{∞+1}\supseteq\bigcup↓iX↓{i+1}=X↓∞$.)

}

\smallskip
{\rmn

\disleft 38pt::{\bf Exercise.}
Why is $X↓{∞↑2}\subseteq X↓{∞↑2+1}$?

\disleft 38pt::({\bf Answer.} $X↓{∞↑2}=\bigcup X↓{j∞}\supseteq X↓{j∞}$
for all~$j$; $X↓{∞↑2+1}=f(X↓{∞↑2})\supseteq\bigcup f(X↓{j∞+1})=X↓{j∞}$;
$X↓{∞↑2+1}\supseteq\bigcup X↓{j∞}=X↓{∞↑2}$.)

}

\smallskip
{\rmn

\disleft 38pt::{\bf Exercise.}
Define the $n$tuples of integers by $\langle\,\rangle =0$,
$\langle x↓0,x↓1,\ldots,x↓n\rangle =\pi(x↓0,\langle x↓1,\ldots,x↓n\rangle)$
where $\pi$ is some fixed pairing function. (A~1--1 function mapping
${\bf N}\times {\bf N}$ onto ${\bf N}+1$.) 
Define an ordering of the tuples:

\display 58pt:$\bullet$:
If $m<n$, any $m$ tuple precedes any $n$ tuple.

\display 58pt:$\bullet$:
For tuples of the same length, they are ordered by the first component
in which they differ.

\disleft 38pt::
$\langle\,\rangle < \langle 0\rangle <
\langle 1\rangle <
\langle 2\rangle <\cdots <\langle 0,0\rangle <\langle 0,1\rangle <\cdots <
\langle 1,0\rangle <\cdots <\langle 2,0\rangle <\cdots <\langle 0,0,0\rangle
<\cdots\,$. Let $h(X)$ be the singleton first $n$tuple not in~$X$;
if $X$ contains all $n$tuples, let $h(X)$ be $\{0\}$. Let $f(X)=X\cup h(X)$.
Show $f$ is monotone. What is~$X↓i$? $X↓∞$? $X↓{2∞+3}$? $X↓{∞↑5}$? $L↓f$?

}


\bigskip
\parindent0pt
\copyright 1987 Robert W. Floyd.
First draft (not published)
September 10, 1987.
%revised date;
%subsequently revised.

\bye